P3831 [SHOI2012]回家的路

这道题显然是最短路,但是似乎转向时不好处理,于是我们要用到分层图。

实现很简单,建立两层图,第一层记录横向边,第二层记录纵向边,相同的关键点两层图连一条费用为1的边。

还有,这道题只需要在关键点之间连边(非关键点无法转向,连了也没用),路径长度为坐标差*2。

阅读全文 »

P4400 [JSOI2008]Blue Mary的旅行

这道题貌似很多人用的是网络流+分层图。这里介绍一种费用流解法。

可以证明,最后一个人到达的时间是小于第100天的。

那么对于每一趟航班,如果他的起点是uu,终点为vv,可搭乘的人的数量为ww。那我们就对(u,v)(u,v)连100条流量为ww,费用为ii的边(ii表示第几天),分别表示第ii天的航班。

阅读全文 »

CF999E Reachability from the Capital

显然,在一个强联通分量中,只要有一个城市与ss联通,那么整个分量就与ss联通。

于是我们可以缩点,统计它的入度。如果入度为00,我们就从ss向这个缩点连一条边,如果入度不为0,说明其他城市可以到达它,我们就不需要单独连边。

最后,注意特判与ss在同一强联通分量的点。

阅读全文 »

P2831 愤怒的小鸟

首先,我们得知道过原点与两点的抛物线解析式:

设该函数解析式为 y=ax2+bx+c(a<0)y=ax^2+bx+c(a < 0)且过 (0,0),(x1,y1),(x2,y2)(0,0),(x_1,y_1),(x_2,y_2) 三点。

由函数过 (0,0)(0,0)c=0c=0

阅读全文 »

P4778 Counting swaps

对于每个位置 ii , 我们向 pip_i 连一条边。 结合题意可知,一个合法的排列,是一个由 nn 个自环组成的图。

但现在会形成多个环,不妨记环的数量为 kk , 第 ii 个环的大小为 sis_i(包括自环)。

我们现在要做的,就是将这 kk 个环拆成 nn 个自环。

阅读全文 »